The present disclosure relates to determining routes in a transportation system, such as a public bus, train or plane system. More specifically, the present disclosure relates to efficiently determining routes in a transportation system for providing alternative choices to travelers within the transportation system.
Study and analysis of transportation systems generally focus on improving efficiency within the transportation system. One typical area of study is traveling from a starting point to a finishing point as fast and efficiently as possible. Such study and analysis has resulted in multiple algorithms and simulation techniques for answering the question “how do I find the shortest and least costly path?”
To answer this question, analysts have traditionally used graph path finding algorithms that substitute nodes for places within the transportation system and iteratively search for links between the nodes to identify paths from one node to another. Implementation of the algorithms typically creates a graph of the determined paths within the system in ascending cost order (e.g., an ordered listing of total resources required to traverse a particular path). Thus, through further analysis of the graph, the algorithm can identify the shortest paths. These graph exploration algorithms perform well for road network analysis where preprocessing techniques can identify shortcuts and graph partitions to greatly improve the computation time.
However, when considering a public transportation system, several problems arise. One problem is that when a time dimension is added, the shortest path becomes dependent upon the time or origin, and thus considerably increases the number of possible paths. For example, taking a bus at 12:00 PM may be quicker to get from point A to B than using the light rail, but at 12:05 PM the light rail may be the shorter way. Another problem includes monitoring and updating changes to the graph of the public transportation system in real-time (or, for example, in near real-time such as 15 minute intervals). Such a time demand renders most preprocessing techniques useless, as they often require several hours to analyze the data. Thus, real-time changes to the public transportation system may be missed. To continue the above example, if the bus is running six minutes late (i.e., not arriving until 12:06 PM), it is now faster to take the light rail instead of the bus.
Thus, when adding public transportation systems to road network analysis, there has been a considerable addition of computational time required. For the average trip planner such a delay may not be noticeable as an addition of five or ten seconds computational time may be negligible. However, for more advanced real-time trip planners, waiting a few seconds becomes unpractical, either because the trip-planner is, for example, a scheduling server for a transportation system that performs a high number of route analysis routines at a time, or because the trip planner is a monitoring system sub-routine that is called thousands of time per second by another module (such as a public transportation network analysis module).
As one solution to these added problems, Microsoft Research introduced the round-based public transit routing (RAPTOR) algorithm where, rather than considering a graph based algorithm, the algorithm considers dynamic optimization of multi-criteria journeys (e.g., considering time and number of transfers as is common in a public transportation network). The RAPTOR algorithm may be used to analyze a network to identify journeys in a round by round process. In each round, the algorithm may be used to scan marked routes keeping the shortest time at each stop, and marks routes for next round analysis if new routes are determined to be reachable earlier. The RAPTOR algorithm exploits the intrinsic nature of the public transportation network where each round can be viewed simply as a traveler making a transfer. The RAPTOR algorithm also identifies reachable bi-criteria shortest paths an order of magnitudes faster than existing algorithms. Additional information related to the RAPTOR algorithm can be found in U.S. Pat. No. 8,494,771 entitled “Journey Planning in Public Transportation Networks,” the content of which is hereby incorporated by reference in its entirety.
Basically, the RAPTOR algorithm scans available information and stores the information in a data structure such as a linked list or database. The stored information is optimized (e.g., presorted or processed to determine specific data about the information such as node or link characteristics), and an optimal solution is output based upon the input query (e.g., the shortest route between points A and B). When analyzing data, overall performance may be the most important characteristic of the RAPTOR algorithm, and potential solutions or choices may be overlooked to improve performance.
While the RAPTOR algorithm can be effective for determining a shortest path in a transportation system, it is not sufficient to provide alternative paths. If a user desires several options, or if a transportation interruption occurs and alternatives need to be identified, existing systems cannot adequately provide alternative recommendations. If additional variables are introduced in an analysis, such as introducing an option to walk to one of multiple points of origin, the required processing time is still prohibitive.
This document describes methods and systems that address at least some of the problems described above, and/or other problems.